This application generally relates to networks, and more specifically to communications in a network.
Collective communication generally involves global data movement and global control among a group of nodes in a network. Many scientific applications exhibit the need of such collective communication patterns. For example, efficient support for collective communication may significantly reduce communication latency and simplify the programming of parallel computers. Collective communication has received much attention in telecommunication and parallel processing in recent years.
All-to-all communication is one type of collective communication. In all-to-all communication, every node in a group sends a message to each other node in the group. Depending on the nature of the message to be sent, all-to-all communication can be further classified as all-to-all broadcast and all-to-all personalized exchange. In all-to-all broadcast, every node sends the same message to all other nodes. In all-to all personalized exchange, every node sends a distinct message to every other node. All-to-all broadcast and all-to-all personalized exchange may be used in networking and parallel computational applications. For example, all-to-all broadcasting may be used in performing matrix multiplication, LU-factorization, and Householder transformations. All-to-all personalized exchange may be used, for example, in performing matrix transposition and fast Fourier transforms (FFTs).
Techniques for all-to-all personalized exchange have been considered in different types of networks. A first class of techniques is used in a high-dimensional network type, such as the hypercube. One drawback of using the first class of techniques in a high-dimensional network type is the poor scalability due to the unbounded node degrees of the high-dimensional network topology.
A second class of techniques have been developed for use in mesh and torus networks. These techniques have an advantage over the first techniques in that these network types have bounded node degrees and are more scalable. However, these second techniques used in the mesh and torus networks have a drawback in that long communications delays may be experienced in all-to-all personalized exchange due to the network topology.
Thus, there is required a technique for performing all-to-all personalized exchanges which is scalable while simultaneously seeking to minimize communication delays.